home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / route.arc / BFS < prev    next >
Encoding:
Text File  |  1989-11-24  |  1.5 KB  |  29 lines
  1. BFS Algorithm  (* breadth-first search *)
  2.    (* Search a graph or state space, depending on the problem definition. *)
  3.    (* S is the start node, T is the goal node. *)
  4.    (* Open is an ordered list of nodes (ordered by arrival time; nodes enter
  5.       at the tail and leave at the head), also called a queue. Closed is a set
  6.       of nodes (order doesn't matter). In general, nodes that need to be
  7.       searched are put on Open. As they are searched, they are removed from
  8.       Open and put in Closed. *)
  9.    (* Pred is defined for each node, and is a list of "came from" indications,
  10.       so when we finally reach T, we traverse Pred to construct a path to S. *)
  11. 1  Open <- {S}  (* a list of one element *)
  12.    Closed <- {}  (* the empty set *)
  13.    Pred[S] <- NULL,  found <- FALSE
  14.    WHILE Open <> {} and not found DO
  15. 5     x <- the first node on Open
  16.       Open <- Open - {x}  (* remove x from Open *)
  17.       Closed <- Closed + {x}  (* put x in Closed *)
  18.       IF x = T THEN found <- TRUE  (* we're done *)
  19.       ELSE  (* continue search through node x *)
  20. 10       let R be the set of neighboring nodes of x
  21.          FOR each y in R DO
  22.             IF y is not on Open or in Closed THEN
  23.                Pred[y] <- x  (* remember where we came from *)
  24.                Open <- Open + {y}  (* put y on Open (at the tail) *)
  25. 15 IF found THEN
  26.       use Pred[T] to find Pred[Pred[T]] and so on until S is reached
  27.       (* this traces out the solution path in reverse *)
  28.    ELSE T cannot be reached from S
  29.